至少走 \(\max(x,y)\) 步，因为最多能扛起箱子 \(k\) 秒，所以会往回走 \(\max(0,y-x-k)\) 步。
1
2
3
4
| public static void solve() {
int x = io.nextInt(), y = io.nextInt(), k = io.nextInt();
io.println(Math.max(x, y) + Math.max(0, y - x - k));
}
|
排序，然后将数组分为左右两部分，分别代表 \(x,y\) 坐标序列。可以证明，这是最优的。
1
2
3
4
5
6
7
8
9
10
11
12
13
| public static void solve() {
int n = io.nextInt();
int[] a = new int[2 * n];
for (int i = 0; i < 2 * n; i++) {
a[i] = io.nextInt();
}
Arrays.sort(a);
io.println(a[n - 1] - a[0] + a[2 * n - 1] - a[n]);
for (int i = 0; i < n; i++) {
io.println(a[i] + " " + a[i + n]);
}
}
|
对于每个字符串 \(s_{i}\)，我们枚举合并字符串的中心位置，这样就可以知道需要在前缀或后缀补上长度以及总和为多少的字符串，使得合并字符串为幸运的。因为合并字符串的中心位置可能不在当前字符串上，所以我们按照长度从小到大处理字符串，这样可以保证不漏掉任何情况。特别的，每个字符串都可以和自身连接成为幸运串。或者也可以进行预处理，这样就不用排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| public static void solve() {
int n = io.nextInt();
char[][] arr = new char[n][];
for (int i = 0; i < n; i++) {
arr[i] = io.next().toCharArray();
}
Arrays.sort(arr, (s1, s2) -> s1.length - s2.length);
long ans = 0L;
int[][] dp = new int[6][46];
for (char[] s : arr) {
int m = s.length;
int[] sum = new int[m + 1];
for (int j = 0; j < m; j++) {
sum[j + 1] = sum[j] + s[j] - '0';
}
for (int j = m / 2 + 1; j <= m; j++) {
ans += dp[2 * j - m][Math.max(0, 2 * sum[j] - sum[m])];
ans += dp[2 * j - m][Math.max(0, sum[m] - 2 * sum[m - j])];
}
dp[m][sum[m]]++;
}
io.println(ans + n);
}
|
首先构造满足第二个条件的数组 \(b\)，我们让 \(b_{n}=0\)，然后前面的每个元素 \(b_{i}=a_{i}\oplus a_{i+1}\oplus\cdots\oplus a_{n-1}\)，这样就得到满足第二个条件的数组，可以通过后缀异或得到。那么如何让 \(b\) 包含从 \(0\) 到 \(n-1\) 的每个数，因为数据保证总是可以构造出这样的序列，也就是说我们得到的数组 \(b\) 异或某个数，就能够得到目标数组。单独考虑每一位是否需要异或，可以发现，如果该位 \(1\) 的数量大于 \(0\) 的数量就需要进行异或操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| public static void solve() {
int n = io.nextInt();
int[] a = new int[n];
for (int i = 0; i < n - 1; i++) {
a[i] = io.nextInt();
}
for (int i = n - 2; i >= 0; i--) {
a[i] = a[i] ^ a[i + 1];
}
int[] d = new int[30];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 30; j++) {
d[j] += a[i] >> j & 1;
}
}
int mask = 0;
for (int i = 0; i < 30; i++) {
if (d[i] > n - d[i]) {
mask |= 1 << i;
}
}
for (int i = 0; i < n; i++) {
io.print((a[i] ^ mask) + " ");
}
io.println();
}
|